# -*- coding: utf-8 -*-
# author: AZJ
# date: 2024/11/20
# 假如命运扼住了你的咽喉，你就去挠她的咯吱窝
from typing import List
'''
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
'''
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:

        """
        方法一、暴力破解
        每次遇到"1"时, 用这个1作为正方形的左上角，想下一行扩展一步，看看最多能可扩展多少
        maxSide = max(maxSide, 1)
        扩展方法:
        当 matrix[i][j] == "1", 开始一个循环, 循环上限为: currentMaxSide =  min(y-i, x-j)
        for k in range(1, currentMaxSide):
            循环体中查看每一列新添内容是否为 1
            if matrix[i+k][j+k] == "0":
                break
            for m in range(k):
                if matrix[i+k][j+m] == "0" or matrix[i+m][j+k] == "0":
                    flag = False
                    break
            if flag:
                maxSide = max(maxSide, k+1)
            else:
                break
        """

        '''
        方法2, 动态规划
        dp[i][j]表示在以(i,j)为右下角，且只包含1的正方形的边长最大值。
        dp[i][j]由dp[i-1][j-1]/dp[i-1][j]/dp[i][j-1]三者共同决定
        dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
        '''
        y = len(matrix)
        x = len(matrix[0])
        dp = [[0 for _ in range(x)] for _ in range(y)]
        maxSide = 0
        for i in range(y):
            for j in range(x):
                if matrix[i][j] == "1":
                    dp[i][j] = 1
        if y <= 1:
            return max(dp[0])
        for i in range(1, y):
            for j in range(1, x):
                if dp[i][j] == 0:
                    continue
                dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
                maxSide = max(maxSide, dp[i][j])

        return maxSide * maxSide


if __name__ == '__main__':
    s = Solution()
    print(s.maximalSquare([["1","0","1","0","0"],
                           ["1","0","1","1","1"],
                           ["1","1","1","1","1"],
                           ["1","0","0","1","0"]]))